package com.heap;

/**
 * IndexMaxHeap : 索引最大堆
 * <p>
 * 将每一个存储的元素分配一个索引存储在 indexes[] 中(索引类似 id 号),然后使得 indexes[] 构成一个最大堆,这样对索引的操作就与元素本身无关.
 * 特性:
 * >若想查看某个索引对应的元素,使用 data[indexes] 即可
 * >对于外界的调用者来说,索引是从 0 开始计数的,而在这个索引堆中,我们使用的时候跳过了 indexes[0],因此在返回索引时,需要使 index - 1;
 */
public class IndexMaxHeap {
    private int[] data; //最大堆的载体,使用数组来承载
    private int num;    //记录传入的最大空间,防止数组越界
    private int count;  //记录已经存储的数量
    private int[] indexes;  //表示索引的数组

    //插入元素时使用,注意 k 表示下标
    private void shiftUp(int k) {
        //在判断的时候,需要判断真正的值
        while ((data[indexes[k / 2]] < data[indexes[k]]) && (k > 1)) {
            //而在交换的时候,只需要交换索引的位置就好 indexes[k/2] 与 indexes[k]
            int temp = indexes[k / 2];
            indexes[k / 2] = indexes[k];
            indexes[k] = temp;
            //更新k,现在data[k/2]即为新插入的那个值
            k /= 2;
        }
    }

    //删除节点时使用,注意 k 表示下标
    //所有的比较都是比较真实的元素,而所有的交换都只是交换索引 indexes[]
    private void shiftDown(int k) {
        while (2 * k <= count) {
            int j = 2 * k;  //表示此轮循环中, data[k] 要和 data[j] 交换位置
            if (2 * k + 1 <= count && data[indexes[j + 1]] > data[indexes[j]]) {
                j += 1;
            }
            if (data[indexes[k]] >= data[indexes[j]]) {
                break;
            }
            int temp = indexes[k];
            indexes[k] = indexes[j];
            indexes[j] = temp;
            k = j;
        }
    }

    public int getCount() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }


    //索引堆在插入新的元素时, i 表示索引,从 0 开始计数
    public void insert(int i, int item) {
        //todo 动态添加空间
//        if (count + 1 > num) {
//            int[] newDate = new int[(int) (num * 1.5)];
//        }

        //防止数组越界
        assert count + 1 <= num;
        assert (i >= 0 && i + 1 <= count);

        //将新加入的数据放在堆的末尾,然后使用完全二叉树的性质进行排序
        data[count + 1] = item;
        count++;
        shiftUp(count);
    }

    //删除最大的节点
    public int extrackMax() {
        assert count > 0;
        //删除节点
        int item = data[indexes[1]];
        int temp = indexes[1];
        indexes[1] = indexes[count];
        count--;
        shiftDown(1);
        return item;
    }

    //返回最大值的索引
    int extractMaxIndex() {
        assert count > 0;
        //注意外部调用的时候索引是从 0 开始的,因此需要 -1
        int index = indexes[1] - 1;
        //将 indexes[1] 直接用最后一个索引覆盖掉
        indexes[1] = indexes[count];
        count--;
        shiftDown(1);
        return index;
    }

    //通过索引得到具体元素
    int getElementByIndex(int i) {
        return data[i + 1];
    }

    //改变索引为 index 的值,变成 newdata
    void changeElementByIndex(int index, int newdata) {
        index += 1;


    }

    public IndexMaxHeap(int num) {
        data = new int[num + 1];
        this.indexes = new int[num + 1];
        this.count = 0;
        this.num = num;
    }
}
